package com.algoruthm6;

import java.util.Arrays;


public class HeapSort {

    public static void sort(int[] array){
        buildHeap(array,array.length);
        for(int i=array.length-1;i>=0;i--){
            Utils.swap(array,0,i);
            heapify(array,i-1,0);
        }
    }
    public static void buildHeap(int[] array,int len){
        for(int i=array.length/2;i>=0;i--){
            heapify(array,len,i);
        }
        System.out.println("heapify结果:" + Arrays.toString(array));
    }

    public static void heapify(int[] array,int len,int k){
        int max = k;
        int left = 2*k+1;
        int right = 2*k+2;
        if(left<len && array[left]>array[max]){
            max = left;
        }
        if(right<len && array[right]>array[max]){
            max = right;
        }
        if(max!=k){
            Utils.swap(array,max,k);
            heapify(array,len,max);
        }

    }
    public static void main(String[] args){
        int[] array = new int[]{8, 9, 3,10, 2, 4, 5, 6, 7, 1};
         //buildHeap(array,array.length);
        sort(array);
        System.out.println("result:"+ Arrays.toString(array));
    }


}
